package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

/**
 * 错误写法
 *
 * @author tzp
 * @since 2020/9/15
 */
public class LC375_1 implements DynamicProblem {
    public int getMoneyAmount(int n) {
        if (n <= 1) return 0;
        if (n == 2) return 1;

        int[] state = new int[n + 1];
        state[0] = 0;
        state[1] = 0;
        state[2] = 1;
        int[] nums = new int[n + 1];
        nums[0] = 0;
        nums[1] = 0;
        nums[2] = 1;
        for (int i = 3; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            int minNum = 1;
            for (int j = 2; j < i; j++) {//j为轴
                int lchildMinMax = state[j - 1];
                int rchildMinMax = j * nums[i - j] + state[i - j];//buggggg这个乘也不对啊....???
                //bugggg失效原因: state[i]和nums[i]记录了猜测i的最倒霉付钱数(18块)和付钱次数(2次), 但是不代表整体base-j之后, 依旧是最倒霉付钱次数(2次).
                //也就是f1-11是18, f6-16可不是18!!
                if (lchildMinMax > rchildMinMax) {
                    if (lchildMinMax + j < min) {
                        min = lchildMinMax + j;
                        minNum = nums[j - 1] + 1;
                    }
                } else {
                    if (rchildMinMax + j < min) {
                        min = rchildMinMax + j;
                        minNum = nums[i - j] + 1;
                    }
                }
            }
            state[i] = min;
            nums[i] = minNum;
        }
        return state[n];
    }

    public static void main(String[] args) {
        //6 ->8, 不是9!!!
        //12 21:9+f(8),
        //16 34
        System.out.println(new LC375_1().getMoneyAmount(16));
    }
}
